package 二叉树;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 会玩的洋洋
 * https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
 */
public class _235_二叉搜索树的最近公共祖先 {
    /**
     * 一次遍历
     * 如果两个节点均小于 ancestor（父节点）的val 则两个节点位于左子树中
     * 如果两个节点均大于 ancestor（父节点）的val 则两个节点位于右子树中
     * 如果两个节点一个大于 一个小于  则公共父节点即为 ancestor 相当于该子树根节点
     * @param root 根节点
     * @param p target1
     * @param q target2
     * @return TreeNode
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode ancestor = root;
        while (true) {
            if (p.val > ancestor.val && q.val > ancestor.val) {
                ancestor = ancestor.right;
            } else if (p.val < ancestor.val && q.val < ancestor.val) {
                ancestor = ancestor.left;
            } else {
                break;
            }
        }
        return ancestor;
    }

    /**
     * 两次遍历
     * 通过查询各自的路径节点
     * 然后遍历节点路径， 如果路径相同，则代表是公共父节点
     * 若分叉，即路径不同时，上一个节点即为最近父节点
     * @param root 根节点
     * @param p target1
     * @param q target2
     * @return TreeNode
     */
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> path_q = getPath(root, q);
        List<TreeNode> path_p = getPath(root, p);
        TreeNode ancestor = null;
        for (int i = 0; i < path_p.size() && i < path_q.size(); i++) {
            if (path_p.get(i) == path_q.get(i)) {
                ancestor = path_p.get(i);
            } else {
                break;
            }
        }
        return ancestor;
    }
    public List<TreeNode> getPath(TreeNode node, TreeNode target) {
        List<TreeNode> path = new ArrayList<>();
        while (node != target) {
            path.add(node);
            if (node.val < target.val) {
                node = node.right;
            } else if (node.val > target.val) {
                node = node.left;
            }
        }
        path.add(node);
        return path;
    }
}
